#同样是两种方法


class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack,rst=[root],[]
        while stack:
            i=stack.pop()
            if isinstance(i,TreeNode):
                #z注意入栈顺序
                stack.extend([i.right,i.left,i.val])
            elif isinstance(i,int):
                rst.append(i)
        return rst

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack,rst=[],[]
        top=root
        while stack or top:
            while top:
                rst.append(top.val)
                stack.append(top)
                top=top.left
            top=stack.pop()
            top=top.right
        return rst